package com.data.construct.linkedList;

/**
 * 链表基本原理
 *
 * @author sunhl
 * @Description:
 * @Date: created in 2024/10/21 0021 10:16
 * @Modified By:
 */
public class LinkedListBasicToKnow {

    public static void main(String[] args) {
        // ========单链表的基本操作=============

        // 创建一条单链表
        createLinkedList(new int[]{1, 2, 3, 4, 5});

        // 遍历单链表
        forEachLinkedList();

        // 在单链表头部插入一个新节点 0
        addHead();

        // 在单链表尾部插入一个新节点 6
        addLast();

        // 在第 3 个节点后面插入一个新节点 66
        addMid();

        // 删除第 4 个节点
        delMid();

        // 删除尾部
        delLast();

        // 删除头部
        delHead();

        // ========双链表的基本操作=============
        // 创建一条双链表
        createDoublyLinkedList(new int[]{1, 2, 3, 4, 5});

        // 遍历双链表
        forEachDoublyListNode();

        // 在双链表头部插入新节点 0
        addHeadDoublyListNode();

        // 在双链表尾部插入新节点 6
        addLastDoublyListNode();

        // 在第 3 个节点后面插入新节点 66
        addMidDoublyListNode();

        // 删除第 4 个节点
        delMidDoublyListNode();

        // 删除头结点
        delHeadDoublyListNode();

        // 删除尾节点
        delTailDoublyListNode();
    }

    // ========单链表的基本操作=============

    /**
     * 输入一个数组，转换为一条单链表
     *
     * @param arr
     * @return
     */
    public static SingelListNodeForShow createLinkedList(int[] arr) {
        if (null == arr || arr.length == 0) {
            return null;
        }

        SingelListNodeForShow head = new SingelListNodeForShow(arr[0]);

        SingelListNodeForShow cur = head;
        for (int i = 1; i < arr.length; i++) {
            head.next = new SingelListNodeForShow(arr[i]);
            cur = head.next;
        }

        return cur;
    }

    /**
     * 遍历单链表
     */
    private static void forEachLinkedList() {
        // 创建一条单链表
        SingelListNodeForShow head = createLinkedList(new int[]{1, 2, 3, 4, 5});

        for (SingelListNodeForShow p = head; p != null; p = p.next) {
            System.out.println(p.val);
        }
    }

    /**
     * 单链表头部插入一个新节点 0
     *
     * @return
     */
    private static SingelListNodeForShow addHead() {
        SingelListNodeForShow head = createLinkedList(new int[]{1, 2, 3, 4, 5});

        SingelListNodeForShow newHead = new SingelListNodeForShow(0);
        newHead.next = head;
        head = newHead;
        // 现在链表变成了 0 -> 1 -> 2 -> 3 -> 4 -> 5
        return head;
    }

    /**
     * 在单链表尾部插入一个新节点 6
     */
    private static void addLast() {
        SingelListNodeForShow head = createLinkedList(new int[]{1, 2, 3, 4, 5});

        SingelListNodeForShow p = head;
        // 先走到链表的最后一个节点
        while (p.next != null) {
            p = p.next;
        }
        // 现在 p 就是链表的最后一个节点
        // 在 p 后面插入新节点
        p.next = new SingelListNodeForShow(6);
        // 现在链表变成了 1 -> 2 -> 3 -> 4 -> 5 -> 6
    }

    /**
     * 在第 3 个节点后面插入一个新节点 66
     */
    private static void addMid() {
        SingelListNodeForShow head = createLinkedList(new int[]{1, 2, 3, 4, 5});

        // 先要找到前驱节点，即第 3 个节点
        SingelListNodeForShow p2 = head;
        for (int i = 0; i < 2; i++) {
            p2 = p2.next;
        }
        // 此时 p 指向第 3 个节点
        // 组装新节点的后驱指针
        SingelListNodeForShow newNode2 = new SingelListNodeForShow(66);
        newNode2.next = p2.next;
        // 插入新节点
        p2.next = newNode2;
        // 现在链表变成了 1 -> 2 -> 3 -> 66 -> 4 -> 5
    }

    /**
     * 删除第 4 个节点
     */
    private static void delMid() {
        // 创建一条单链表
        SingelListNodeForShow head = createLinkedList(new int[]{1, 2, 3, 4, 5});
        SingelListNodeForShow p = head;
        // 删除第 4 个节点，要操作前驱节点
        for (int i = 0; i < 2; i++) {
            p = p.next;
        }
        // 此时 p 指向第 3 个节点，即要删除节点的前驱节点
        // 把第 4 个节点从链表中摘除
        p.next = p.next.next;

        // 现在链表变成了 1 -> 2 -> 3 -> 5
    }

    /**
     * 删除尾部
     */
    private static void delLast() {
        // 创建一条单链表
        SingelListNodeForShow head = createLinkedList(new int[]{1, 2, 3, 4, 5});

        // 删除尾节点
        SingelListNodeForShow p = head;
        // 找到倒数第二个节点
        while (p.next.next != null) {
            p = p.next;
        }

        // 此时 p 指向倒数第二个节点
        // 把尾节点从链表中摘除
        p.next = null;

        // 现在链表变成了 1 -> 2 -> 3 -> 4
    }

    /**
     * 删除头部
     */
    private static void delHead() {
        // 创建一条单链表
        SingelListNodeForShow head = createLinkedList(new int[]{1, 2, 3, 4, 5});

        // 删除头结点
        head = head.next;

        // 现在链表变成了 2 -> 3 -> 4 -> 5
    }

    // ========双链表的基本操作=============

    /**
     * 创建双链表
     *
     * @param arr
     * @return
     */
    public static DoublyListNodeForShow createDoublyLinkedList(int[] arr) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        DoublyListNodeForShow head = new DoublyListNodeForShow(arr[0]);
        DoublyListNodeForShow cur = head;
        // for 循环迭代创建双链表
        for (int i = 1; i < arr.length; i++) {
            DoublyListNodeForShow newNode = new DoublyListNodeForShow(arr[i]);
            cur.next = newNode;
            newNode.prev = cur;
            cur = cur.next;
        }
        return head;
    }

    /**
     * 遍历双链表
     */
    private static void forEachDoublyListNode() {
        // 创建一条双链表
        DoublyListNodeForShow head = createDoublyLinkedList(new int[]{1, 2, 3, 4, 5});
        DoublyListNodeForShow tail = null;

        // 从头节点向后遍历双链表
        for (DoublyListNodeForShow p = head; null != p; p = p.next) {
            System.out.println(p.val);
            // 这里设置尾部是为了后面从尾节点向前遍历双链表能继续
            tail = p;
        }

        // 从尾节点向前遍历双链表
        for (DoublyListNodeForShow p = tail; null != p; p = p.prev) {
            System.out.println(p.val);
        }
    }


    /**
     * 在双链表头部插入新节点 0
     */
    private static void addHeadDoublyListNode() {
        // 创建一条双链表
        DoublyListNodeForShow head = createDoublyLinkedList(new int[]{1, 2, 3, 4, 5});

        // 在双链表头部插入新节点 0
        DoublyListNodeForShow newHead = new DoublyListNodeForShow(0);
        newHead.next = head;
        head.prev = newHead;
        head = newHead;
        // 现在链表变成了 0 -> 1 -> 2 -> 3 -> 4 -> 5
    }

    /**
     * 在双链表尾部插入新节点 6
     */
    private static void addLastDoublyListNode() {
        // 创建一条双链表
        DoublyListNodeForShow head = createDoublyLinkedList(new int[]{1, 2, 3, 4, 5});

        DoublyListNodeForShow tail = head;
        // 先走到链表的最后一个节点
        while (null != tail.next) {
            tail = tail.next;
        }

        // 在双链表尾部插入新节点 6
        DoublyListNodeForShow newNode = new DoublyListNodeForShow(6);
        tail.next = newNode;
        newNode.prev = tail;
        // 更新尾节点引用
        tail = newNode;

        // 现在链表变成了 1 -> 2 -> 3 -> 4 -> 5 -> 6
    }

    /**
     * 在第 3 个节点后面插入新节点 66
     */
    private static void addMidDoublyListNode() {
        // 创建一条双链表
        DoublyListNodeForShow head = createDoublyLinkedList(new int[]{1, 2, 3, 4, 5});

        // 找到第 3 个节点
        DoublyListNodeForShow p = head;
        for (int i = 0; i < 2; i++) {
            p = p.next;
        }

        // 组装新节点
        DoublyListNodeForShow newNode = new DoublyListNodeForShow(66);
        newNode.next = p.next;
        newNode.prev = p;

        // 插入新节点
        p.next.prev = newNode;
        // 这里的要点是第 3 个节点的下一个节点一定要在最后才更新
        p.next = newNode;

        // 现在链表变成了 1 -> 2 -> 3 -> 66 -> 4 -> 5
    }


    /**
     * 删除第 4 个节点
     */
    private static void delMidDoublyListNode() {
        // 创建一条双链表
        DoublyListNodeForShow head = createDoublyLinkedList(new int[]{1, 2, 3, 4, 5});

        // 先找到第 3 个节点
        DoublyListNodeForShow p = head;
        for (int i = 0; i < 2; i++) {
            p = p.next;
        }

        // 现在 p 指向第 3 个节点，我们它后面那个节点摘除出去
        DoublyListNodeForShow toDelete = p.next;
        // 把 toDelete 从链表中摘除
        p.next = toDelete.next;
        p.next.prev = p;

        // 把 toDelete 的前后指针都置为 null 是个好习惯（可选）
        toDelete.next = null;
        toDelete.prev = null;

        // 现在链表变成了 1 -> 2 -> 3 -> 5
    }

    /**
     * 删除头结点
     */
    private static void delHeadDoublyListNode() {
        // 创建一条双链表
        DoublyListNodeForShow head = createDoublyLinkedList(new int[]{1, 2, 3, 4, 5});

        // 删除头结点
        DoublyListNodeForShow toDelete = head;
        head = head.next;
        head.prev = null;

        // 清理已删除节点的指针
        toDelete.next = null;

        // 现在链表变成了 2 -> 3 -> 4 -> 5
    }

    /**
     * 删除尾节点
     */
    private static void delTailDoublyListNode() {
        // 创建一条双链表
        DoublyListNodeForShow head = createDoublyLinkedList(new int[]{1, 2, 3, 4, 5});

        // 删除尾节点
        DoublyListNodeForShow p = head;
        // 找到尾结点
        while (p.next != null) {
            p = p.next;
        }

        // 现在 p 指向尾节点
        // 把尾节点从链表中摘除
        p.prev.next = null;

        // 把被删结点的指针都断开是个好习惯（可选）
        p.prev = null;

        // 现在链表变成了 1 -> 2 -> 3 -> 4
    }

}
